The present invention relates generally to communication systems and methods, and more particularly, to an image compression technique for use with image transmission or communication systems and methods that employs low entropy coding of images and error correction.
Image compression techniques have used several schemes to reduce the number of bits required to store or transfer images. When the images are sent over a communication link there is a possibility of introducing errors.
One technique for compressing images is a transform compression scheme. One transform used in many applications is a discrete cosine transform. Another transform that is used is a wavelet transform. The compression process begins by organizing an image into blocks that are convenient for the transform. For JPEG images, the transform is an 8xc3x978 discrete cosine transform. The result of the image transformation is that most of the energy in the image is captured in low frequency elements of the transform.
The quantization of the transform values introduces errors in the reconstructed image and reduces the information in the image. The amount of the quantization and the technique for quantizing establishes many parameters of the compression. A typical technique involves weighting the transform values according to the frequency, then rounding the transform values to form integers. While truncation may be used, good practice uses rounding since it reduces the amount of the error.
Entropy encoding attempts to use long code words for rare image transform values and very short code words for image transform values that occur often. If the transform matches the image well, the bulk of the energy of the image is captured in a few of the coefficients in a block. The remainder of the coefficients are zero or nearly zero. Since so many quantized coefficients are zero or nearly zero, these coefficients are assigned code values that are very short.
The entropy coded coefficients are typically ordered by the xe2x80x9cfrequencyxe2x80x9d associated with the coefficient. For JPEG lossy compression, the ordering from low frequency to high frequency selects the coefficients in a zigzag pattern over a rectangular array of coefficients that are the output of the transform. The ordering is important, since it organizes the low frequency coefficients where much of the information of the image is concentrated first and leaves the low information, or xe2x80x9clow entropyxe2x80x9d, coefficients until last.
The low entropy portion of the image is a part of the image where many of the values of the quantized transform are the same or nearly the same. The higher frequency coefficients of the quantized transform have many values that are zero or nearly zero, corresponding to the low entropy portion of the image. If the entropy encoding is restricted to encoding the coefficients one at a time, the smallest number of bits per pixel is one.
The number of bits for the low entropy portion of the quantized transform can be strongly reduced by using xe2x80x9crun length encodingxe2x80x9d. When there are many values in a row that are zero, the run of zeroes may be replaced by a special code word followed by the number of zeroes in the string. In this way, a few bits may be used to represent large numbers of pixels in the low entropy part of the image.
With run length encoding, the number of bits per pixel may be reduced to less than one on the average. An image that uses 10 bits per pixel for the image values may be compressed 20:1 to one half bit per pixel on the average. For a large class of images, 20:1 compression yields very pleasing restored images.
An alternative scheme for entropy encoding was suggested by Said and Pearlman in xe2x80x9cA new, fast, and efficient image codec based on set partitioning in hierarchical trees,xe2x80x9d IEEE Trans on Circuits and Systems for Video Technology, Vol. 6, No. 3, June 1996, page 243-250. The quantized transform is first organized by xe2x80x9czero treexe2x80x9d association of the transform values. This association starts with the lowest frequency coefficient and for each coefficient associates the higher frequency coefficients for that location on the image. Since the wavelet transform usually has a 2:1 downsample between levels, each coefficient at the lowest frequency has four coefficients in each of the three next higher frequency set of coefficients associated with the same point. The zero tree ordering of the coefficients results in a natural ordering of the coefficients by frequency. The ordering is important for the Said and Pearlman approach to compression. An alternative for the wavelet transform is to transmit each of the blocks of frequency coefficients independently, starting with the lowest frequency block.
The quantized transform is organized by bit planes. The most significant bit of each quantized transform coefficient in a block is encoded first. In an area where there is much energy, many of the bits may be ones. If the quantized transformed values are organized by frequency, this area is the low frequency parts of the quantized transform.
The higher frequency areas of the high order bits are almost all zero. The result is an ideal application of run length coding. The bit plane for the block is transmitted by sending the first part of the block, then sending the end of the block using run length coding when there are no more ones in the bit plane. The next bit plane is similarly encoded by sending the bits of the bit plane ordered by frequency until there are no more ones in the bit plane, then sending a run length coded string of zeroes.
This technique can be controlled to achieve a given signal-to-noise ratio or a given compression ratio for each block by terminating the bit plane compression at a convenient point depending on the attribute desired. The remainder of the bits are not sent, corresponding to an effective quantization of the image.
When the image is sent through a communication channel, bit errors may be introduced. Bit errors cause the entropy decoder to lose synchronization with the data stream. Until synchronization is reestablished, there are a large number of pixels that are decoded in error. The decoder is typically re-synchronized by adding special markers to the beginning of a line or the beginning of a block. Many fewer lines or blocks will be in error if the transmission scheme reduces the number of transmission errors to a small value. This is achieved by the present invention. At the same time, it would also be desirable to use error correction to improve the image compression by improving the low entropy coding.
From the above, it can be seen that previous techniques use a relatively inefficient run length coding technique for low entropy coding that has minimal resistance to errors in communication. Therefore, it would be an improvement to have image transmission system and method comprising an image compression technique that uses error correction to reduce errors in communication over a communication channel while improving the compression of the image.
To meet the above and other objectives, the present invention provides for a system and method that introduces intentional errors into a compression scheme for images. The intentional errors along with error correction processing enable much improved low entropy encoding of the images. The error correction also serves to reduce the errors in transmission over a communication channel. Furthermore, the present invention uses error correction to improve the compression by improving the low entropy coding.
The system and method compresses images and performs error correction on images that are transmitted through the communication channel that introduces errors into the transmitted data. The present invention thus provides for a technique that improves low entropy coding of images by using an error-correction encoding.
More particularly, the present invention provides for an image transmission system and method. In the system and method an image is blocked to create a plurality of image blocks. The image blocks are transform coded to produce a plurality of transform coefficients. The transform coefficients are quantized. The quantized transform coefficients are entropy coded. In accordance with the principles of the present invention, the entropy coded quantized transform coefficients are error correction coded, and the entropy coded coefficients are truncated to introduce intentional errors into the image that is to be communicated.
The image is then transmitted through a communication channel. In accordance with the principles of the present invention, blocks of the received image are expanded to produce entropy coded coefficients with possible communication errors. The entropy coded coefficients are error correction decoded to produce corrected entropy coded coefficients. Errors corrected are errors introduced by the communication path and errors introduced to make low entropy encoding more efficient. The error correction decoded image blocks are entropy decoded to produce the quantized transform coefficients. The quantized transform coefficients are then inverse quantized to produce the plurality of transform coefficients. The plurality of transform coefficients are inverse transformed to produce the plurality of image blocks. Finally, the plurality of image blocks are unblocked to produce the transmitted image.
Error correction in accordance with the present invention is preferably used in an image transmission system to communicate through a communication channel that introduces errors. The error correction is used to improve the quality of the communicated data. The error correction adds bits to the communication data stream. A scheme that may be used in many applications is a Bose Chaudhuri Hocquenghem encoder. A related encoder is a Reed Solomon encoder. The encoder adds a number of bits or symbols to a block of data to be encoded. An example Reed Solomon encoder adds 24 bytes to a block of 231 bytes to reduce the error rate for a communication channel from 10xe2x88x923 to 10xe2x88x928. The number of bytes added is about 10% of the number of bytes that are encoded.
For compression, the addition of the error correction typically reduces the effective compression by 10%. Instead of achieving 0.5 bits per pixel for 20:1 compression of a 10 bit image, the number of bits per pixel is close to 0.55. Of course, the design of the error correction is part of the communication system design and the percent of added information required for error correction can vary over a wide range depending on the requirements of the communication system.